/**
 题目:
    给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
    注意：答案中不可以包含重复的三元组。
    示例：
    给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    满足要求的三元组集合为：
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]


 思路:
    1. 先排序,然后在一次遍历中使用指针对撞
    2. 利用for循环快速过滤掉重复元素
    3. 当遍历的值大于0后可直接返回结果 利用有序的特性进行剪枝
 效果
    
*/
 
   class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int size=nums.size();
        if(size<3){
            return {};
        }
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        int left=0,right=size-1;
        while(left<size-2){
            if(left>0&&nums[left]==nums[left-1]){
                left++;
                continue;
            }
            int index=left+1;
            int right=size-1;
            
            while(right>index){
                int tmp=nums[left]+nums[index]+nums[right];
                if(tmp==0){
                    vector<int> item;
                    item.push_back(nums[left]);
                    item.push_back(nums[index]);
                    item.push_back(nums[right]);
                    res.push_back(item);
                    while(index<right&&nums[index]==nums[index+1]) index++;
                    while(index<right&&nums[right]==nums[right-1]) right--;
                    index++;
                }else if(tmp>0){
                    //说明值太大了
                    while(index<right&&nums[right]==nums[right-1]) right--;
                    right--;
                }else{
                    while(index<right&&nums[index]==nums[index+1]) index++;
                    index++;
                }
            }
            left++;
        }
        return res;
    }
};